Computational Algebra: Frequently asked questions


Programming assignment 1:

Question: Assignment1, first you talk about 3 ways of computing the polynomial, but then  on the bottom of the page you want it computed in two ways. Which?
Answer: See the expressions for p65. After the first = is the product, after the second = comes the sum. The product can be written directly in Matlab, the sum gives a longer Matlab expression or you will get it by calling the procedure polyval.

 Question: You note that you do not want the entire Matlab code.  Only the interesting part.  My question to you is then how interesting must the lines be for you to want to see them?
Answer:   It is enough if you explain what you have done. In this case that you used the routine poly to find coefficients c and routine polyval to compute the sum. No matlab text necessary for this one.
   The same with the experiments in assignments 3-5.
   In the assignment 2, a program is asked for. Include that one.

Question: What is the growth factor in Assignment 3?
Answer: The quotient between the largest element in the L and U factors and the largest element in the original matrix A (absolute values).

Programming assignment 2:

Question: I'm having i little problem understanding shat exactly it is that we are supposed to do in assignment 2.
First are we supposed solve the problem in 2.1 using both reordering methods ?
 Answer: Yes all 3 orderings Original, RCM and AMD

Question: Second are we expected to use reordering on the full matrix as well ?
Answer: No, ordering has no effect on full matrix code.

Question: I did program Cholesky just as given in the Demmel book p 78 but it was all very slow. Should I use the built in routines from Matlab instead?
Answer: Do  not write Matlab programs at the lowest level where single matrix elements are handled. It will be extremely slow. The program is interpreted and not compiled, so each Matlab operation needs many machine instructions and memory accesses. The Matlab commands like lu, chol and \ calls state of the art routines from LAPACK (Linear Algebra package) which are coded in Fortran and calls machine coded low level routines BLAS (Basic Linear Algebra Subroutines) for vector and matrix operations.  You will learn more about how to program and not to program low level routines on modern workstations in the PDC Summer course DN2258, Thomas Ericsson, has gathered quite a few interesting tips.

Programming assignment 3:

Question: There is three cases in Assignment 2 of the first part 'least squares curve fitting'. do we need to do all the three cases or just choose one to to do?
Answer: Do them all and compare the results.

Question: In assignment 2 should you first form the matrix A of assignment 1 to give a  19 degree polynomial and then vary the number of singular vectors used in finding the low rank approximations.
Answer: Yes, start with the 101*20 matrix of assignment 1, and use an appropriate number of the leading singular vectors. You only need to compute the svd once, then U(:,1:k) is the m*k matrix of the first columns of U. You can also compute  b once and take the first k elements by b(1:k).

Question: When I call
[Q R]=qr(A);
 I get a 101*101 matrix Q. What about the last 81 columns?

Answer: The command qr  gives a square orthogonal matrix Q. The last 81 columns are just the corresponding columns of the unit matrix orthogonalized to the space spanned by first 20 columns. You  are advised to use the economy size qr and svd commands where
[Q R]=qr(A,0);
gives a 101*20 matrix Q with orthogonal columns. The same happens with svd(A,0). Often the number of rows m is much larger than the number of columns n and then this needs much less space.

Question: Where can I find more information on the pattern recognition problem?

Answer: Look at the paper by Lars Elden in Acta Numerica.